プログラムを雑に書かないためにアルゴリズムを知ろう
データインテグレーション部＠札幌の佐藤です。
今までプログラムを雑に書いてませんか？とりあえず動けばよいのではないかそう考えてプログラム書いてませんか？
誰かを煽っているわけではなく、自身へ自戒の念を込めての言葉です。
仕事で運用フェイズにいることが多いため、パフォーマンスに関する問題は少なからず遭遇しています。
そのような経験もあり、開発フェイズ時に運用フェイズを見越した実装ができればいいなと思っているのですが、自身の勉強不足もあって今はなかなか上手くいかないのが現状です。
それを打破したいなという気持ちから、プログラムの勉強の一環としてアルゴリズムを勉強しています。
なぜアルゴリズムを知るのか、「１からNまでの総数の和」をどう出すのかを使って書いていきたいと思います。
アルゴリズムとは
wikipediaには以下のように記載しています。
アルゴリズム（英: algorithm [ˈælgəˌrɪðəm]）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。
https://ja.wikipedia.org/wiki/アルゴリズム
つまり、アルゴリズムはある答えにたどり着くまでの道筋の問題です。
処理を実行したときに正しい回答が出力されるのであれば、ものすごい冗長なコードを書いても問題ありません。
ただ、スパゲッティ化を助長するようなコードを書いても、運用する人が保守できず困るし、実行速度も向上しないし、誰も幸せになりません。
みんなで幸せになろうよ。
できるだけ、みんなが理解できて（≠簡潔化）、処理が早いを目指していければいいということだと思います。
「１からNまでの総数の和」の公式
「１からNまでの総数の和」を考えたときにいくつか案があると思いますが、数学的には以下だと思います。
[latex]1+2+3+…+n=\frac{1}{2}n(n+1)[/latex]
私は文系出身で、大学も言語学や文学をやってきた人間なので、この公式を見たときにどういうことなんだ？レベルの能力しかもっていませんでした。
簡単に説明すると、以下のように長方形を作ります。
緑色とオレンジ色を足し合わせると全て7になるということがわかります。6×7の長方形ですね。
緑色＝ 1＋2＋3＋4＋5＋6
オレンジ色＝ 6＋5＋4＋3＋2＋1
結果としてほしいのはその半分の値なので2で割ることで回答が導き出せます。
もし「１からNまでの総数の和」を実装する場合は、この公式を使ってあげれば実装上問題ないと思います。
でも本当にそうなのでしょうか。
本当にそれが「みんなが理解できて、処理が早い」のでしょうか。
検証
「１から10000までの総数の和」を実装したいくつかのパターンを検証してみます。
実行速度だけではなく、メモリ使用率も見てみます。
ソース
パターン1
from memory_profiler import profile
import time
@profile
def pattern1(n):
s=0
for i in range(n):
s=s+(i+1)
return s
if __name__ == '__main__':
# パターン1
start = time.time()
print(pattern1(10000))
print(time.time() - start)
パターン1は、python的な知見があまりない場合、普通のfor文で処理するのではないかなと思い作ったパターンです。誰でも読みやすいですね。
パターン2
from memory_profiler import profile
import time
@profile
def pattern2(n):
return sum([i+1 for i in range(n)])
if __name__ == '__main__':
# パターン2
start = time.time()
print(pattern2(10000))
print(time.time() - start)
パターン2は、Pythonのfor文の内報表記パターンです。誰でもわかるかというと、何となくやろうとしていることは分かるみたいなレベル感でしょうか。
パターン3
from memory_profiler import profile
import time
@profile
def pattern3(n):
return n*(n+1)/2
if __name__ == '__main__':
# パターン3
start = time.time()
print(pattern3(10000))
print(time.time() - start)
パターン3は、「１からNまでの総数の和」の公式のパターンです。コメントなしでこの公式だけ書いていたら、何の処理をしているのかわからない人もあると思います。（私は分からなかったと思います）
メモリ使用量
パターン1～3の使用メモリ量は以下です。 「Mem usage」は使用されているメモリ量。「Increment」は前行から追加で使用されているメモリ量を表しています。
パターン1
Line # Mem usage Increment Line Contents
================================================
7 53.7 MiB 53.7 MiB @profile
8 def pattern1(n):
9 53.7 MiB 0.0 MiB s=0
10 53.7 MiB 0.0 MiB for i in range(n):
11 53.7 MiB 0.0 MiB s=s+(i+1)
12 53.7 MiB 0.0 MiB return s
パターン2
Line # Mem usage Increment Line Contents
================================================
14 53.8 MiB 53.8 MiB @profile
15 def pattern2(n):
16 54.3 MiB 0.1 MiB return sum([i+1 for i in range(n)])
パターン3
Line # Mem usage Increment Line Contents
================================================
18 53.2 MiB 53.2 MiB @profile
19 def pattern3(n):
20 53.2 MiB 0.0 MiB return n*(n+1)/2
メモリの使用量だけ見るとパターン3が一番消費していないように見えます。 パターン2はreturnで一気に処理するからかメモリ消費量が増えていますね。
実行速度
パターン1 0.5013291835784912 パターン2 0.26267576217651367 パターン3 0.07831406593322754
最短がパターン3の約0.08秒、最長がパターン1の約0.5秒、その差は約0.42秒です。 この時間差をどう見るかは、実装する機能によっても違うと思います。
パターン3は素晴らしいのか
ここから見てもパターン3が一番メモリを使用せず、処理時間も短いので一番優秀に見えます。
ですが、可読性という観点ではどうでしょうか。
必ずしもパターン3が優秀とは限りません。優先される要素によってパターン1や2がとられる可能性もあります。
アルゴリズムを勉強するということは、ある結果に対していくつかのパターンを導き出せるための勉強なのかなと思います。
できるだけ、みんなが理解できて（≠簡潔化）、処理が早いを目指していければいいなと思います。
